import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public int monotoneIncreasingDigits(int n) {
        if(n<10) return n;
        char[] num=Integer.toString(n).toCharArray();

        int i=0;
        while(num[i]<=num[i+1]){
            i++;
            if(i==num.length-1) return n;
        }

        while(i>0&&num[i]==num[i-1]){
            i--;
        }
        num[i]-=1;


        for(int j=i+1;j<num.length;j++){
            num[j]='9';
        }

        String s=String.valueOf(num);   //数组变String要用valueOf,其它用toString
        return Integer.valueOf(s);




    }
}


class Solution1 {
    public int[][] merge(int[][] intervals) {
        ArrayList<int[]> ret=new ArrayList<>();
        Arrays.sort(intervals,(a, b)->a[0]-b[0]);
        int left=0;
        int right=0;
        int i=0;

        for(i=0;i<intervals.length;i++){
            left=intervals[i][0];
            right=intervals[i][1];
            while(i<intervals.length-1&&intervals[i+1][0]<=right){
                right=Math.max(intervals[i+1][1],right);
                i++;
            }
            ret.add(new int[]{left,right});

        }

        return ret.toArray(new int[0][]);


    }
}


class Solution2 {
    public int eraseOverlapIntervals(int[][] intervals) {
        int n=intervals.length;
        int ret=0;
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);

        int right=0;
        int i=0;
        for(i=0;i<n;i++){
            right=intervals[i][1];
            while(i<n-1&&intervals[i+1][0]<right){
                right=Math.min(right,intervals[i+1][1]);
                ret++;
                i++;


            }

        }

        return ret;


    }
}




class Solution5{
    public static void main(String[] args) {
        String r="hdfios";
        String[] ss={"hsdudb","ajopef","ciwhdiow"};
        Arrays.sort(ss);

        System.out.println(ss[0]);

        System.out.println(ss[1]);
        System.out.println(ss[2]);
    }
    public int findMinArrowShots(int[][] points) {
        int n=points.length;
        Arrays.sort(points,(a,b)->Integer.compare(a[0], b[0]));
        long left=0;
        long right=0;
        int ret=0;

        for(int i=0;i<n;i++){

            right=points[i][1];

            while(i<n-1&&points[i+1][0]<=right){

                right=Math.min(right,points[i+1][1]);
                i++;
            }
            ret++;
        }
        return ret;


    }
}